Ad hoc networks are increasingly being used for many applications. For example, ad hoc networks are used for sensing, detection, and tracking, and are being applied in military, ecological, environmental, and domestic system applications for monitoring and/or control. Ad hoc networks are also being used to automate buildings, universities, factories, etc.
Typically, the terminals of an ad hoc network are randomly and arbitrarily deployed in such a manner that their locations are not necessarily known a priori. The terminals of an ad hoc network may be stationary or mobile. The terminals of an ad hoc network are preferably, although not necessarily, wireless terminals.
Ad hoc networks generally operate over a single channel. Thus, a transmission by one terminal in the network is heard by all other terminals within range of the transmitting terminal. Terminals communicate among themselves in a multi-hop fashion so that a terminal that wants to transmit to another terminal that is not within its transmission range will transmit to a terminal that is within its transmission and that terminal will transmit to another terminal and so until the transmission arrives at the desired terminal.
Collisions of transmissions occur when two or more terminals within each other's transmission range transmit simultaneously in the same channel. As a result of such collisions, each of the terminals involved in the collision will attempt a retransmission. Every such retransmission causes a delay in message communication, lowers network throughput, and significantly drains the battery life of the terminal.
Many medium access control (MAC) protocols have been developed that attempt to minimize the drain on battery power of the terminals due to the retransmissions resulting from collisions. Time division multiplexing is one approach that has been used to reduce collision between terminals. Time division multiplexing based scheduling algorithms are superior to CSMA-CD based protocols for wireless ad hoc networks and, hence, are preferable wherever it is possible to use time division multiplexing.
Various algorithms are known that attempt to optimize channel allocation in cellular mobile networks. These algorithms attempt to optimally assign frequencies (channels) in cellular networks while assuming different frequency separation constraints. In channel allocation, a two-cell buffering constraint may be used during allocation.
When transmissions in an ad hoc network are based on a time division multiplexing model, existing implementations of time slot assignment attempt to assign a globally unique time slot to each terminal in the network, usually through graph coloring techniques, or by finding an appropriate set of partitions of the set of terminals and then assigning a unique time slot to each of these partitions. The ultimate goal is that no two terminals transmit during the same time slot.
Many of these implementations use more time slots (non-optimal assignment) than the optimal solution. Also, the number of time slots increases rapidly with an increase in the maximum terminal degree of the network graph, although the average terminal degree may be very small. It is also known to use a maximal independent set of terminals to generate a self-organizing time division multiple access schedule.
The pre-existence of a partitioning of the ad hoc network deployment area into a number of disjoint cells has been proposed in several works. The hexagonal cellular structure is assumed to be the conceptually closest approximation to the actually circular circumference of an omni-directional transmission radius while providing a regular cell structure. Therefore, the hexagonal cellular structure is widely used for modeling cellular communication networks.
To form a cellular structure within an ad hoc network, a mapping is used to convert a geographical region to hexagonal grid cells. It is known that time division multiplexing scheduling algorithms for wireless ad hoc networks partition an ad hoc network into hexagonal cellular networks, and that GPS enabled devices or terminals are used in ad hoc networks. Algorithms are also known that execute on terminals and that use the network infrastructure to determine locations of terminals relative to the deployment zone. GPS can provide highly accurate and synchronized global time, besides accurate location information. The knowledge of geographical information by terminals in an ad hoc network is an increasingly popular assumption to provide precise location and timing synchronization information. The current generation of mobile phones are GPS enabled, and there is ongoing research to improve GPS indoors. In the absence of GPS, a relative coordinate system can be used.
The present invention relates to a new approach to determining a collision-free transmission schedule for networks, such as ad hoc networks, using time division multiplexing.